package someTestExcemple.huaweiOd.container.tree;

//华为OD机试 - 创建二叉树（Java 2024 E卷 200分）
//https://blog.csdn.net/guorui_java/article/details/142637532
import java.util.*;
public class CreateBinaryTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入的操作字符串
        String inputLine = scanner.nextLine();

        // 解析输入字符串为二维整数数组
        Integer[][] operations = Arrays.stream(
                        inputLine.substring(1, inputLine.length() - 1)
                                .split("(?<=]), (?=\\[)")
                )
                .map(operationStr -> Arrays.stream(
                                        operationStr.substring(1, operationStr.length() - 1).split(", ")
                                )
                                .map(Integer::parseInt)
                                .toArray(Integer[]::new)
                )
                .toArray(Integer[][]::new);

        // 构建二叉树并输出结果
        System.out.println(buildBinaryTree(operations));
    }

    /**
     * 根据操作列表构建二叉树，并返回层序遍历结果的字符串表示。
     *
     * @param operations 每个操作包含高度和索引，用于添加子节点
     * @return 层序遍历结果的字符串表示
     */
    public static String buildBinaryTree(Integer[][] operations) {
        // 初始化根节点，值为 -1
        Node root = new Node(-1);

        // 存储每一层的节点列表，初始化第一层包含根节点
        List<Node> currentLevel = new ArrayList<>();
        currentLevel.add(root);

        // 存储所有层的节点，treeLevels.get(h) 获取第 h 层的节点列表
        List<List<Node>> treeLevels = new ArrayList<>();
        treeLevels.add(currentLevel);

        // 遍历每个操作，依次添加节点
        for (int i = 0; i < operations.length; i++) {
            int height = operations[i][0];
            int index = operations[i][1];

            // 如果当前树的层数不足以包含目标高度的下一层，则添加新的层
            if (treeLevels.size() <= height + 1) {
                treeLevels.add(new ArrayList<>());
            }

            // 创建新子节点，值为当前操作的索引 i
            Node childNode = new Node(i);

            // 获取目标父节点
            Node parentNode = treeLevels.get(height).get(index);

            // 如果父节点有空的子节点位置，则将新节点添加到下一层
            if (parentNode.leftChild == null || parentNode.rightChild == null) {
                treeLevels.get(height + 1).add(childNode);
            }

            // 将新节点分配为父节点的左子节点或右子节点
            if (parentNode.leftChild == null) {
                parentNode.leftChild = childNode;
            } else if (parentNode.rightChild == null) {
                parentNode.rightChild = childNode;
            }
        }

        // 进行层序遍历，记录节点值
        LinkedList<Integer> levelOrderValues = new LinkedList<>();
        LinkedList<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(treeLevels.get(0).get(0)); // 从根节点开始

        while (!nodeQueue.isEmpty()) {
            Node currentNode = nodeQueue.removeFirst();

            if (currentNode != null) {
                levelOrderValues.add(currentNode.value);
                nodeQueue.add(currentNode.leftChild);
                nodeQueue.add(currentNode.rightChild);
            } else {
                levelOrderValues.add(null);
            }
        }

        // 移除层序遍历结果末尾的多余 null 值
        while (!levelOrderValues.isEmpty() && levelOrderValues.getLast() == null) {
            levelOrderValues.removeLast();
        }

        // 将结果列表转换为字符串格式
        StringJoiner result = new StringJoiner(", ", "[", "]");
        for (Integer val : levelOrderValues) {
            result.add(val != null ? val.toString() : "null");
        }

        return result.toString();
    }
}

/**
 * 定义二叉树的节点结构。
 */
class Node {
    int value;
    Node leftChild;
    Node rightChild;

    public Node(int value) {
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }
}
